\relax 
\citation{Penber94}
\citation{Penber94}
\citation{Smith99}
\citation{Bacchus01}
\citation{Haslum01}
\citation{Gerevi02}
\citation{Kvarnstrom03}
\citation{Younes03}
\citation{Wah06}
\citation{Gerevini08}
\citation{Eyerich09}
\citation{Gerevini10}
\citation{PDDL21}
\citation{Cushing07}
\citation{Cushing07}
\citation{Do03}
\citation{IPC6}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}}
\newlabel{sec:intro}{{1}{1}}
\citation{Rao04}
\citation{Carman03,Rao04}
\citation{smith:jair03}
\citation{do:icaps2008}
\citation{Cushing07:ICAPS}
\citation{Shin:aaai04}
\citation{Coles08}
\citation{Coles08:AIJ}
\citation{Gerevini10}
\citation{Eyerich09}
\citation{Li04}
\citation{zhang:CAV-02}
\newlabel{fig:scop}{{1}{3}}
\@writefile{toc}{\contentsline {section}{\numberline {2}Background}{3}}
\newlabel{sec:background}{{2}{3}}
\citation{Fox03pddl2.1}
\citation{Coles08}
\citation{Kautz92,Kautz96}
\newlabel{def:plan}{{2.3}{4}}
\newlabel{def:depc}{{2.5}{4}}
\@writefile{toc}{\contentsline {section}{\numberline {3}SAT-based CSTE Planning Framework}{4}}
\newlabel{sec:encoding}{{3}{4}}
\citation{Li04}
\citation{Long03}
\newlabel{overall}{{1}{5}}
\@writefile{loa}{\contentsline {algocf}{\numberline {1}{\ignorespaces A SAT-based CSTE Planning  Framework (SCP)}}{5}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Extended SAT formulations}{5}}
\newlabel{def:mincost}{{3.1}{5}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Transformation of actions}{5}}
\citation{Smith99}
\citation{Kautz92}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}MinCost SAT encoding}{6}}
\citation{Kautz04}
\citation{Smith99}
\citation{Davis62,zhang:CAV-02}
\citation{Marques96}
\citation{Moskewicz:DAC-01}
\citation{Planes03,Fu06,Larrosa09}
\citation{Een:TAST-04}
\@writefile{toc}{\contentsline {section}{\numberline {4}A Branch-and-Bound Algorithm for Solving MinCost SAT}{7}}
\newlabel{sec:opt}{{4}{7}}
\newlabel{bb-dpll}{{2}{8}}
\@writefile{loa}{\contentsline {algocf}{\numberline {2}{\ignorespaces  BB-DPLL($\Phi ^c$) }}{8}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Lower bounding based on relaxed planning}{8}}
\newlabel{sec.relax}{{4.1}{8}}
\citation{Bonet01}
\citation{Nguyen02}
\citation{Fu06}
\citation{Larrosa09}
\citation{Blum97,Hoffmann01}
\newlabel{fig:plangraph}{{2}{9}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.1.1}Theory}{9}}
\newlabel{def:cont}{{4.1}{10}}
\newlabel{def:f-cont}{{4.1}{10}}
\newlabel{def:o-cont}{{4.1}{10}}
\newlabel{def:indepset}{{4.2}{10}}
\newlabel{def:h-x}{{4.3}{10}}
\newlabel{def:h-neg}{{4.3}{10}}
\newlabel{def:h-fact}{{4.3}{10}}
\newlabel{def:h-action}{{4.3}{10}}
\newlabel{def:h-goal}{{1}{11}}
\newlabel{lemm:h-x}{{4.4}{11}}
\newlabel{the:h-v}{{1}{11}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.1.2}Implementation}{11}}
\citation{zhang:CAV-02,Een:TAST-04}
\citation{Moskewicz:DAC-01}
\@writefile{loa}{\contentsline {algocf}{\numberline {3}{\ignorespaces cost\_init()}}{12}}
\newlabel{costinit}{{3}{12}}
\newlabel{costprop}{{4}{12}}
\@writefile{loa}{\contentsline {algocf}{\numberline {4}{\ignorespaces cost\_propagate()}}{12}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Action cost based variable branching}{12}}
\newlabel{sec.branch}{{4.2}{12}}
\citation{Een:TAST-04}
\citation{Coles08}
\citation{Coles08}
\citation{Coles08}
\@writefile{toc}{\contentsline {section}{\numberline {5}Experimental Results}{13}}
\newlabel{sec:experiments}{{5}{13}}
\citation{Bhattacharya07}
\citation{Coles08}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}Testing domains}{14}}
\citation{Coles08}
\citation{Coles08}
\citation{IPC3}
\citation{Coles08}
\citation{Coles08:AIJ}
\citation{Coles08}
\citation{Gerevi02}
\citation{Eyerich09}
\citation{huang09:ICAPS}
\citation{Een:TAST-04}
\citation{sat4j}
\citation{maxsat09}
\newlabel{illuActions}{{3}{16}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}Results of temporal expressive planners}{16}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.1}The P2P domain}{16}}
\newlabel{p2pResult}{{I}{17}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.2}The Matchlift domain}{17}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.3}The Matchlift-Variant domain}{17}}
\newlabel{ma_result}{{II}{18}}
\newlabel{mar_result}{{III}{18}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.4}The Driverslogshift domain}{18}}
\citation{Robinson08,huang:AAAI10}
\citation{Chen09}
\citation{Fu06}
\newlabel{dr_result}{{IV}{19}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.5}Number of variables and clauses}{19}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.3}Effectiveness of lower bounding and variable branching techniques}{19}}
\newlabel{sec:opt-res}{{5.3}{19}}
\newlabel{var_result}{{V}{20}}
\newlabel{fig:cost-1}{{4}{20}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {P2P}}}{20}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Matchlift}}}{20}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {Matchlift-Variant}}}{20}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {Driverslogshift}}}{20}}
\newlabel{fig:time-1}{{5}{21}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {P2P}}}{21}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Matchlift}}}{21}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {Matchlift-Variant}}}{21}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {Driverslogshift}}}{21}}
\citation{Mausam06,Cushing07}
\citation{Penber94}
\citation{Smith99}
\citation{Bacchus01}
\citation{Haslum01}
\citation{Gerevi02}
\citation{Long03}
\citation{Kvarnstrom03}
\citation{Younes03}
\citation{Do03}
\citation{Wah06}
\citation{Vidal06}
\citation{Gerevini08}
\citation{Shin:aaai04}
\citation{Coles08}
\citation{Coles08:AIJ}
\citation{Gerevini10}
\citation{Eyerich09}
\citation{Wolfman99}
\citation{Gerevini10}
\citation{Eyerich09}
\citation{Hu07}
\citation{Refanidis01}
\citation{Do03}
\citation{Richter08,Richter10}
\citation{Haslum08}
\citation{keyder08}
\citation{Robinson08-coplan}
\citation{vidal:IPC-04,haslum:ICAPS-00,buttner:ICAPS-05,helmert:AAAI08}
\citation{IPC08a}
\citation{Giu07}
\citation{Robinson10}
\citation{Giu:JELIA-06}
\citation{Robinson10}
\citation{Coudert96}
\citation{Manquinho02}
\citation{Li04}
\citation{Fu06}
\citation{Fu06,Moskewica01}
\citation{Fu06}
\@writefile{toc}{\contentsline {section}{\numberline {6}Related Work}{22}}
\newlabel{sec:related}{{6}{22}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.1}Temporal planning}{22}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.2}Cost sensitive planners}{22}}
\citation{Borchers97}
\citation{Alsinet03}
\citation{Shen02}
\citation{Xing05maxsolver}
\citation{Heras07minimaxsat,Heras07minimaxsat-b}
\citation{Dixon02}
\citation{Givry03}
\citation{sat4j}
\citation{Darras07}
\citation{Li06,Li07,Li09}
\citation{Pipatsrisawat07clone}
\bibstyle{acmsmall}
\bibdata{huang,lu}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.3}SAT solvers}{23}}
\@writefile{toc}{\contentsline {section}{\numberline {7}Conclusions and Future Work}{23}}
\newlabel{sec:discussions}{{7}{23}}
\bibcite{Alsinet03}{\citeauthoryear {Alsinet, Manya, and Planes}{Alsinet et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2003}}
\bibcite{Bacchus01}{\citeauthoryear {Bacchus and Winter}{Bacchus and Winter}{2001}}
\bibcite{Bhattacharya07}{\citeauthoryear {Bhattacharya and Ghosh}{Bhattacharya and Ghosh}{2007}}
\bibcite{Blum97}{\citeauthoryear {Blum and Furst}{Blum and Furst}{1997}}
\bibcite{Bonet01}{\citeauthoryear {Bonet and Geffner}{Bonet and Geffner}{2001}}
\bibcite{Borchers97}{\citeauthoryear {Borchers and Furman}{Borchers and Furman}{1997}}
\bibcite{buttner:ICAPS-05}{\citeauthoryear {B{\"u}ttner and Rintanen}{B{\"u}ttner and Rintanen}{2005}}
\bibcite{Carman03}{\citeauthoryear {Carman, Serafini, and Traverso}{Carman et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2003}}
\bibcite{Chen09}{\citeauthoryear {Chen, Huang, Xing, and Zhang}{Chen et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2009}}
\bibcite{IPC08a}{\citeauthoryear {Chen, Lv, and Huang}{Chen et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2008}}
\bibcite{Coles08:AIJ}{\citeauthoryear {Coles, Fox, Halsey, Long, and Smith}{Coles et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2008}}
\bibcite{Coles08}{\citeauthoryear {Coles, Fox, Long, and Smith}{Coles et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2008}}
\bibcite{Coudert96}{\citeauthoryear {Coudert}{Coudert}{1996}}
\bibcite{Cushing07}{\citeauthoryear {Cushing, Kambhampati, Mausam, and Weld}{Cushing et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2007}}
\bibcite{Cushing07:ICAPS}{\citeauthoryear {Cushing, Kambhampati, Talamadupula, Weld, and Mausam}{Cushing et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2007}}
\bibcite{Darras07}{\citeauthoryear {Darras, Dequen, Devendeville, and Li}{Darras et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2007}}
\bibcite{Davis62}{\citeauthoryear {Davis, Logemann, and Loveland}{Davis et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{1962}}
\bibcite{Dixon02}{\citeauthoryear {Dixon and Ginsberg}{Dixon and Ginsberg}{2002}}
\bibcite{Do03}{\citeauthoryear {Do and Kambhampati}{Do and Kambhampati}{2003}}
\bibcite{do:icaps2008}{\citeauthoryear {Do, Ruml, and Zhou}{Do et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2008}}
\bibcite{Een:TAST-04}{\citeauthoryear {E\'{e}n and S\"{o}rensson}{E\'{e}n and S\"{o}rensson}{2004}}
\bibcite{Eyerich09}{\citeauthoryear {Eyerich, Mattm{\"u}ller, and R{\"o}ger}{Eyerich et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2009}}
\bibcite{PDDL21}{\citeauthoryear {Fox and Long}{Fox and Long}{2003a}}
\bibcite{Fox03pddl2.1}{\citeauthoryear {Fox and Long}{Fox and Long}{2003b}}
\bibcite{Fu06}{\citeauthoryear {Fu and Malik}{Fu and Malik}{2006}}
\bibcite{Gerevini08}{\citeauthoryear {Gerevini, Saetti, and Serina}{Gerevini et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2008}}
\bibcite{Gerevini10}{\citeauthoryear {Gerevini, Saetti, and Serina}{Gerevini et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2010}}
\bibcite{Gerevi02}{\citeauthoryear {Gerevini and Serina}{Gerevini and Serina}{2002}}
\bibcite{Giu:JELIA-06}{\citeauthoryear {Giunchiglia and Maratea}{Giunchiglia and Maratea}{2006}}
\bibcite{Giu07}{\citeauthoryear {Giunchiglia and Maratea}{Giunchiglia and Maratea}{2007}}
\bibcite{Givry03}{\citeauthoryear {Givry, Larrosa, Meseguer, and Schiex}{Givry et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2003}}
\bibcite{Haslum08}{\citeauthoryear {Haslum}{Haslum}{2008}}
\bibcite{haslum:ICAPS-00}{\citeauthoryear {Haslum and Geffner}{Haslum and Geffner}{2000}}
\bibcite{Haslum01}{\citeauthoryear {Haslum and Geffner}{Haslum and Geffner}{2001}}
\bibcite{helmert:AAAI08}{\citeauthoryear {Helmert, Haslum, and Hoffmann}{Helmert et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2008}}
\bibcite{Heras07minimaxsat}{\citeauthoryear {Heras, Larrosa, and Oliveras}{Heras et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2007}}
\bibcite{Heras07minimaxsat-b}{\citeauthoryear {Heras, Larrosa, and Oliveras}{Heras et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2008}}
\bibcite{Hoffmann01}{\citeauthoryear {Hoffmann and Nebel}{Hoffmann and Nebel}{2001}}
\bibcite{Hu07}{\citeauthoryear {Hu}{Hu}{2007}}
\bibcite{huang09:ICAPS}{\citeauthoryear {Huang, Chen, and Zhang}{Huang et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2009}}
\bibcite{huang:AAAI10}{\citeauthoryear {Huang, Chen, and Zhang}{Huang et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2010}}
\bibcite{IPC3}{\citeauthoryear {IPC}{IPC}{2004}}
\bibcite{IPC6}{\citeauthoryear {IPC}{IPC}{2008}}
\bibcite{Kautz04}{\citeauthoryear {Kautz}{Kautz}{2004}}
\bibcite{Kautz92}{\citeauthoryear {Kautz and Selman}{Kautz and Selman}{1992}}
\bibcite{Kautz96}{\citeauthoryear {Kautz and Selman}{Kautz and Selman}{1996}}
\bibcite{keyder08}{\citeauthoryear {Keyder and Geffner}{Keyder and Geffner}{2008}}
\bibcite{Kvarnstrom03}{\citeauthoryear {Kvarnstr{\"o}m and Magnusson}{Kvarnstr{\"o}m and Magnusson}{2003}}
\bibcite{Larrosa09}{\citeauthoryear {Larrosa, Nieuwenhuis, Oliveras, and Rodr\'{\i }guez-Carbonell}{Larrosa et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2009}}
\bibcite{Li09}{\citeauthoryear {Li, Manya, Mohamedou, and Planes}{Li et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2009}}
\bibcite{Li06}{\citeauthoryear {Li, Manya, and Planes}{Li et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2006}}
\bibcite{Li07}{\citeauthoryear {Li, Manya, and Planes}{Li et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2007}}
\bibcite{Li04}{\citeauthoryear {Li}{Li}{2004}}
\bibcite{Long03}{\citeauthoryear {Long and Fox}{Long and Fox}{2003}}
\bibcite{Manquinho02}{\citeauthoryear {Manquinho and Marques-Silva}{Manquinho and Marques-Silva}{2002}}
\bibcite{Marques96}{\citeauthoryear {Marques-Silva and Sakallah}{Marques-Silva and Sakallah}{1996}}
\bibcite{Mausam06}{\citeauthoryear {Mausam and Weld}{Mausam and Weld}{2006}}
\bibcite{Moskewica01}{\citeauthoryear {Moskewicz, Madigan, Zhao, Zhang, and Malik}{Moskewicz et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2001a}}
\bibcite{Moskewicz:DAC-01}{\citeauthoryear {Moskewicz, Madigan, Zhao, Zhang, and Malik}{Moskewicz et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2001b}}
\bibcite{Nguyen02}{\citeauthoryear {Nguyen, Kambhampati, and Nigenda}{Nguyen et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2002}}
\bibcite{Penber94}{\citeauthoryear {Penberthy and Weld}{Penberthy and Weld}{1994}}
\bibcite{Pipatsrisawat07clone}{\citeauthoryear {Pipatsrisawat and Darwiche}{Pipatsrisawat and Darwiche}{2007}}
\bibcite{Planes03}{\citeauthoryear {Planes}{Planes}{2003}}
\bibcite{Rao04}{\citeauthoryear {Rao and Su}{Rao and Su}{2004}}
\bibcite{Refanidis01}{\citeauthoryear {Refanidis, , Refanidis, and Vlahavas}{Refanidis et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2001}}
\bibcite{Richter08}{\citeauthoryear {Richter and Westphal}{Richter and Westphal}{2008}}
\bibcite{Richter10}{\citeauthoryear {Richter and Westphal}{Richter and Westphal}{2010}}
\bibcite{Robinson08}{\citeauthoryear {Robinson, Gretton, Pham, and Sattar}{Robinson et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2008}}
\bibcite{Robinson08-coplan}{\citeauthoryear {Robinson, Gretton, and Pham}{Robinson et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2008}}
\bibcite{Robinson10}{\citeauthoryear {Robinson, Gretton, Pham, and Sattar}{Robinson et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2010}}
\bibcite{sat4j}{\citeauthoryear {{SAT4J solver}}{{SAT4J solver}}{2004}}
\bibcite{Shen02}{\citeauthoryear {Shen and Zhang}{Shen and Zhang}{2002}}
\bibcite{Shin:aaai04}{\citeauthoryear {Shin and Davis}{Shin and Davis}{2004}}
\bibcite{smith:jair03}{\citeauthoryear {Smith}{Smith}{2003}}
\bibcite{Smith99}{\citeauthoryear {Smith and Weld}{Smith and Weld}{1999}}
\bibcite{maxsat09}{\citeauthoryear {{The Fourth {Max-SAT} Evaluation}}{{The Fourth {Max-SAT} Evaluation}}{2009}}
\bibcite{vidal:IPC-04}{\citeauthoryear {Vidal and Geffner}{Vidal and Geffner}{2004}}
\bibcite{Vidal06}{\citeauthoryear {Vidal and Geffner}{Vidal and Geffner}{2006}}
\bibcite{Wah06}{\citeauthoryear {Wah and Chen}{Wah and Chen}{2006}}
\bibcite{Wolfman99}{\citeauthoryear {Wolfman and Weld}{Wolfman and Weld}{1999}}
\bibcite{Xing05maxsolver}{\citeauthoryear {Xing and Zhang}{Xing and Zhang}{2005}}
\bibcite{Younes03}{\citeauthoryear {Younes and Simmons}{Younes and Simmons}{2003}}
\bibcite{zhang:CAV-02}{\citeauthoryear {Zhang and Malik}{Zhang and Malik}{2002}}
\lastpage{26}
\@writefile{toc}{\contentsline {section}{\numberline {Appendix A}Proofs}{App--1}}
\newlabel{appendix:proofs}{{Appendix A}{App--1}}
\citation{maxsat09}
\@writefile{toc}{\contentsline {section}{\numberline {Appendix B}Weighted Partial Max-SAT}{App--2}}
\newlabel{appendix:maxsat}{{Appendix B}{App--2}}
\newlabel{def:maxsat}{{B.1}{App--2}}
\@writefile{toc}{\contentsline {section}{\numberline {Appendix C}Experimental Results of MinCost SAT Solvers}{App--3}}
\newlabel{appendix:cost-time}{{Appendix C}{App--3}}
\newlabel{tb:p2p}{{VI}{App--4}}
\newlabel{tb:matchlift}{{VII}{App--4}}
\newlabel{tb:matchliftv}{{VIII}{App--4}}
\newlabel{tb:driverlog}{{IX}{App--5}}
